package cuit.pymjl;

import cuit.entity.TreeNode;
import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.stream.IntStream;

/**
 * @author Pymjl
 * @version 1.0
 * @date 2022/7/16 15:12
 **/
public class Algorithm {
    @Test
    void test() {
        Set<Integer> set = new HashSet<>();
        System.out.println(set.add(1));
        System.out.println(set.add(1));
        Map<String, Integer> map = new HashMap<>();
        map.put("a", 1);
        map.put("b", 2);
        System.out.println(map.getOrDefault("a", 0));
        System.out.println(map.getOrDefault("c", 0));

    }

    @Test
    void testTree() {
        int[] inorder = {-4, -10, 3, -1, 7, 11, -8, 2};
        int[] postorder = {-4, -1, 3, -10, 11, -8, 2, 7};
        TreeNode root = buildTree1(inorder, postorder);
    }

    public TreeNode buildTree1(int[] inorder, int[] postorder) {
        return getTree1(inorder, 0, inorder.length, postorder, 0, postorder.length);

    }

    public TreeNode getTree1(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        //如果没有元素了，则退出递归
        if (inEnd - inStart < 1) return null;
        //如果只有一个元素
        if (inEnd - inStart == 1) return new TreeNode(inorder[inStart]);
        //将后序数组中的最后一个元素作为当前节点
        TreeNode root = new TreeNode(postorder[postEnd - 1]);
        //找到分割数组的节点下标
        int delimiter = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == root.val) {
                delimiter = i;
                break;
            }
        }
        //递归分割左树,后续左/右数组的长度必然和中序左/右数组的长度相同，以此来分割
        root.left = getTree1(inorder, inStart, delimiter, postorder, postStart, postStart + delimiter - inStart);
        root.right = getTree1(inorder, delimiter + 1, inEnd, postorder, postStart + delimiter - inStart, postEnd - 1);
        return root;
    }

    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        return getTree2(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    public TreeNode getTree2(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        //如果没有元素了，则退出递归
        if (preEnd - preStart < 1) return null;
        //如果只有一个元素
        if (preEnd - preStart == 1) return new TreeNode(preorder[preStart]);
        //将前序数组中的第一个元素作为当前节点
        TreeNode root = new TreeNode(preorder[preStart]);
        //找到分割数组的节点下标
        int delimiter = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == root.val) {
                delimiter = i;
                break;
            }
        }
        //递归分割左树,后续左/右数组的长度必然和中序左/右数组的长度相同，以此来分割
        root.left = getTree2(preorder, preStart + 1, preStart + delimiter - inStart + 1, inorder, inStart, delimiter);
        root.right = getTree2(preorder, preStart + delimiter - inStart + 1, preEnd, inorder, delimiter + 1, inEnd);
        return root;
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return getTree3(nums, 0, nums.length);
    }

    private TreeNode getTree3(int[] nums, int start, int end) {
        //如果没有元素了，直接返回null
        if (end - start < 1) return null;
        //如果仅有一个元素
        if (end - start == 1) return new TreeNode(nums[start]);
        //找到最大值
        int maxIndex = start;
        int maxValue = nums[maxIndex];
        for (int i = maxIndex + 1; i < end; i++) {
            if (maxValue < nums[i]) {
                maxIndex = i;
                maxValue = nums[i];
            }
        }
        //以最大值构造节点
        TreeNode root = new TreeNode(maxValue);
        //以最大值的下标来分割构造最大的二叉树
        root.left = getTree3(nums, start, maxIndex);
        root.right = getTree3(nums, maxIndex + 1, end);
        return root;
    }

    @Test
    void reversePrint() {
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(Arrays.toString(IntStream.rangeClosed(1, array.length).mapToObj(i -> array[array.length - i]).toArray()));
    }

    List<List<Integer>> res = new ArrayList<>();
    Deque<Integer> path = new LinkedList<>();
    int sum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //先排序
        Arrays.sort(candidates);
        //标记数组
        boolean[] used = new boolean[candidates.length];
        getSum(candidates, target, used, 0);
        return res;
    }

    private void getSum(int[] candidates, int target, boolean[] used, int startIndex) {
        //结束条件
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        //循环
        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
            //先进行去重
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            sum += candidates[i];
            path.push(candidates[i]);
            getSum(candidates, target, used, i + 1);
            path.pop();
            sum -= candidates[i];
            used[i] = false;
        }

    }

    @Test
    void testMain() {
        int[] array = {10, 1, 2, 7, 6, 1, 5};
        System.out.println(combinationSum2(array, 8));
    }

    List<List<String>> resStringList = new ArrayList<>();
    Deque<String> deque = new LinkedList<>();

    public List<List<String>> partition(String s) {
        getString(s, 0);
        return resStringList;
    }

    private void getString(String s, int startIndex) {
        //结束条件
        if (startIndex >= s.length()) {
            resStringList.add(new ArrayList<>(deque));
            return;
        }
        //循环分割
        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindrome(s, startIndex, i)) {
                //如果是回文串，就加入path
                deque.addLast(s.substring(startIndex, i + 1));
            } else {
                continue;
            }
            getString(s, i + 1);
            deque.removeLast();

        }
    }

    //判断是否是回文串
    private boolean isPalindrome(String s, int startIndex, int end) {
        for (int i = startIndex, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }

    @Test
    void testStringMain() {
        System.out.println(partition("aab"));
    }

    public int movingCount(int m, int n, int k) {
        if (k == 0) {
            return 1;
        }
        boolean[][] vis = new boolean[m][n];
        int ans = 1;
        vis[0][0] = true;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i == 0 && j == 0) || get(i) + get(j) > k) {
                    continue;
                }
                // 边界判断
                if (i - 1 >= 0) {
                    vis[i][j] |= vis[i - 1][j];
                }
                if (j - 1 >= 0) {
                    vis[i][j] |= vis[i][j - 1];
                }
                ans += vis[i][j] ? 1 : 0;
            }
        }
        return ans;
    }

    private int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }

    @Test
    void testStringIp() {
        System.out.println(restoreIpAddresses("19812300"));

    }

    List<String> resStringIp = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s == null || s.length() > 12) return resStringIp;
        getIpString(s, 0, 0);
        return resStringIp;
    }

    public void getIpString(String s, int startIndex, int pointNum) {
        //终止条件
        if (pointNum == 3) {
            //判断最后一段子串是否合法
            if (isValid(s, startIndex, s.length() - 1)) {
                resStringIp.add(new String(s));
            }
        }
        //单层搜索
        for (int i = startIndex; i < s.length(); i++) {
            //剪枝
            if (isValid(s, startIndex, i)) {
                //添加“.”
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                pointNum++;
                getIpString(s, i + 2, pointNum);
                //回溯
                s = s.substring(0, i + 1) + s.substring(i + 2);
                pointNum--;
            } else {
                break;
            }
        }

    }

    public boolean isValid(String s, int start, int end) {
        //索引越界，不合法
        if (start > end) return false;
        //首字母不能为0
        if (s.charAt(start) == '0' && start != end) return false;
        //判断数字
        int num = 0;
        for (int i = start; i <= end; i++) {
            //非法字符直接返回
            if (s.charAt(i) < '0' || s.charAt(i) > '9') return false;
            //判断数字是否大于255
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) return false;
        }
        return true;
    }
}